#include <string>
#include <iostream>
#include <vector>

using namespace std;

/**
 * 基数排序
 * @param a 待排序数组
 * @param length 数组长度
 * @param m 最大位数
 */
void radixSort(string a[], int length, int m);

void radixSort(string a[], int length, int m) {
    int size = 20;// 桶的个数 考虑正负号和每个数字是0-9,所以有20个桶, 依次存放-9,-8...,-1,负数的0,整数的0,1,2,3..9
    // 桶容器
    vector<vector<string>> vec;
    for (int i = 0; i < size; ++i) {
        vector<string> v;
        vec.push_back(v);
    }

    // d表示第几位开始比较, 1表示个位, 2表示十位...
    int d = 1;

    // 进行m轮循环
    // 依次对个位 十位.. 进行排序, 如果当前位不存在数字用0代替
    for (int i = 0; i < m; ++i) {
        // 用0初始化b
        for (int i = 0; i < vec.size(); ++i) {
            vec[i].clear();
        }
        for (int j = 0; j < length; ++j) {
            // 如果位数不够, 正数放入第11个桶(存储正数的0),负数放入第10个桶(存储负数的0)
            int x = 10;
            if (a[j][0] != '-') {
                // 正数的情况
                if (a[j].length() >= d) {
                    // 取出d位的char, 并转成数字.
                    x = 10 + a[j][a[j].length() - d] - 48;
                } else {
                    x = 10;
                }
            } else {
                // 负数的情况
                if (a[j].length() - 1 >= d) {
                    // 取出d位的char, 并转成数字.
                    x = 9 - (a[j][a[j].length() - d] - 48);
                } else {
                    x = 9;
                }
            }

            // 添加到桶中
            vec[x].push_back(a[j]);
        }

        // 排序, 依次把桶中的数据放回原数组
        int num = 0;
        for (int j = 0; j < vec.size(); ++j) {
            for (int k = 0; k < vec[j].size(); ++k) {
                a[num++].assign(vec[j][k]);
            }
        }
        // 准备进行下一位比较
        d++;
    }
}

/**
 * 比较s[i]与目标k的大小
 * @param s 数组
 * @param i 索引i
 * @param k 目标字符换数字
 * @return true表示s[i] > k; false表示s[i]<k
 */
bool compare(string s[], int i, string k);

bool compare(string s[], int i, string k) {
    //s[i]>k,return true
    int a = s[i].length(), b = k.length();

    if (k[0] == '-' && s[i][0] != '-') {
        return true;
    } else if (s[i][0] != '-' && k[0] != '-') {
        if ((a > b) || (a == b && s[i] > k)) {
            return true;
        }
    } else if (s[i][0] == '-' && k[0] == '-') {
        if ((a < b) || (a == b && s[i] < k)) {
            return true;
        }
    }
    return false;
}

/**
 * 交换两个字符串
 * @param a 字符串a
 * @param b 字符串b
 */
void change(string &a, string &b);

void change(string &a, string &b) {
    string t = a;
    a = b;
    b = t;
}

/**
 * 判断数组p是否有序
 * @param p 数组
 * @param n 元素个数
 * @return no|yes
 */
string isSorted(string p[], int n);

string isSorted(string p[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        if (compare(p, i, p[i + 1])) {
            return "no";
        }
    }
    return "yes";
}


/**
 * 希尔排序
 * @param p 待排序数组
 * @param n 数组长度
 */
void shellSort(string p[], int n);

void shellSort(string p[], int n) {
    int step = 0;//步长
    string temp;//用来保存第二段数据
    int i, j;

    for (step = n / 2; step > 0; step /= 2) {
        for (i = step; i < n; i++) {

            temp.assign(p[i]);
            for (j = i - step; j >= 0 && compare(p, j, temp); j -= step) {
                //当满足条件时第一次j+step = i;后面的j+step = 上一次j的值
                p[j + step].assign(p[j]);
            }
            p[j + step].assign(temp);
        }
    }
}

/**
 * 快速排序
 * @param a 待排序数组
 * @param start 数据区间的最小索引
 * @param end 数据区间的最大索引
 */
void quickSortArray(string a[], int start, int end);

void quickSortArray(string a[], int start, int end) {
    if (start >= end)
        return;
    int i = start, j = end;
    string k = a[start];
    while (i != j) {
        while (i < j && compare(a, j, k))
            j--;
        change(a[i], a[j]);
        while (i < j && !compare(a, i, k))
            i++;
        change(a[i], a[j]);
    }
    quickSortArray(a, start, i);
    quickSortArray(a, i + 1, end);
}


/**
 * 快速排序
 * @param a 待排序数组
 * @param length 数组长度
 */
void quickSort(string a[], int length);

void quickSort(string a[], int length) {
    quickSortArray(a, 0, length - 1);
}


// 合并
void merge(string arr[], string tempArr[], int left, int mid, int right);

void merge(string arr[], string tempArr[], int left, int mid, int right) {
    // 标记左半区第一个未排序的元素
    int l_pos = left;
    // 标记右半区第一个未排序的元素
    int r_pos = mid + 1;
    // 临时数组元素的下标
    int pos = left;

    // 合并
    while (l_pos <= mid && r_pos <= right) {
        //if (arr[l_pos] < arr[r_pos])  // 左半区第一个剩余元素更小
        if (compare(arr, r_pos, arr[l_pos]))//s[i]>k
            // tempArr[pos++] = arr[l_pos++];
            tempArr[pos++].assign(arr[l_pos++]);
        else  // 右半区第一个剩余元素更小
            // tempArr[pos++] = arr[r_pos++];
            tempArr[pos++].assign(arr[r_pos++]);
    }

    // 合并左半区剩余的元素
    while (l_pos <= mid)
        //tempArr[pos++] = arr[l_pos++];
        tempArr[pos++].assign(arr[l_pos++]);

    // 合并右半区剩余的元素
    while (r_pos <= right)
        //tempArr[pos++] = arr[r_pos++];
        tempArr[pos++].assign(arr[r_pos++]);

    // 把临时数组中合并后的元素复制回原来的数组
    while (left <= right) {
        //arr[left] = tempArr[left];
        arr[left].assign(tempArr[left]);
        left++;
    }
}

// 归并排序
void msort(string arr[], string tempArr[], int left, int right);

void msort(string arr[], string tempArr[], int left, int right) {
    // 如果只有一个元素，那么不需要继续划分
    // 只有一个元素的区域，本生就是有序的，只需要被归并即可
    if (left < right) {
        // 找中间点
        int mid = (left + right) >> 1;
        // 递归划分左半区
        msort(arr, tempArr, left, mid);
        // 递归划分右半区
        msort(arr, tempArr, mid + 1, right);
        // 合并已经排序的部分
        merge(arr, tempArr, left, mid, right);
    }
}

// 归并排序入口
void mergeSort(string arr[], int n);

void mergeSort(string arr[], int n) {

    // 分配一个辅助数组
    string *tempArr = new string[n];
    // 调用实际的归并排序
    msort(arr, tempArr, 0, n - 1);
}

/**
 * 选择排序
 * @param p 待排序数组
 * @param n 数组长度
 */
void selectSort(string p[], int n);

void selectSort(string p[], int n) {
    int i, j;
    // 记录最小数的索引
    int minIndex = 0;
    for (i = 0; i < n - 1; i++)//排序次数
    {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (compare(p, minIndex, p[j])) {
                minIndex = j;
            }
        }

        if (i != minIndex) {
            change(p[i], p[minIndex]);
        }
    }
}

/**
 * 复制数组
 * @param src 原数组
 * @param dest 目标数组
 * @param length 数组长度
 */
void copyArray(string src[], string dest[], int length);
void copyArray(string src[], string dest[], int length){
    for (int i = 0; i < length; ++i) {
        dest[i].assign(src[i]);
    }

    /*for (int i = 0; i < length; ++i) {
        cout << dest[i] << " ";
    }
    cout << endl;*/
}

int main() {
//    freopen("test.txt", "r", stdin);
    int n;
    while (cin >> n) {
        // 记录最大数据的位数
        int maxLength = 0;
        string *s = new string[n];

        for (int i = 0; i < n; i++) {
            cin >> s[i];
            if (maxLength < s[i].length()) {
                maxLength = s[i].length();
            }
        }

        cout << "----------radixSort----------" << endl;
        string radixArray[n];
        copyArray(s, radixArray, n);
        radixSort(radixArray, n, maxLength);
        cout << "Is array sorted: " << isSorted(radixArray, n) << endl;
        cout << endl;

        cout << "----------quickSort----------" << endl;
        string quickArray[n];
        copyArray(s, quickArray, n);
        quickSort(quickArray, n);
        cout << "Is array sorted: " << isSorted(quickArray, n) << endl;
        cout << endl;

        cout << "----------mergeSort----------" << endl;
        string mergeArray[n];
        copyArray(s, mergeArray, n);
        mergeSort(mergeArray, n);
        cout << "Is array sorted: " << isSorted(mergeArray, n) << endl;
        cout << endl;

        cout << "----------shellSort----------" << endl;
        string shellArray[n];
        copyArray(s, shellArray, n);
        shellSort(shellArray, n);
        cout << "Is array sorted: " << isSorted(shellArray, n) << endl;
        cout << endl;

        cout << "----------selectSort----------" << endl;
        selectSort(s, n);
        cout << "Is array sorted: " << isSorted(s, n) << endl;
        cout << endl;
    }
    return 0;
}